package puzzle.projecteuler.p300;

import java.math.BigInteger;

public class Problem250C {

	/**
	 * answer	: 1425480602091519
	 * time cost: 48859 ms
	 * @param args
	 */
	public static void main(String[] args) {

		long start = System.currentTimeMillis();

		BigInteger[] A = new BigInteger[250];
		for (int j = 0; j < A.length; j ++) {
			A[j] = BigInteger.ZERO;
		}
		BigInteger[] B = new BigInteger[250];
		
		BigInteger n250 = BigInteger.valueOf(250);
		int[] C = new int[500];
		for (int j = 0; j < C.length; j ++) {
			BigInteger t = BigInteger.valueOf(j+1);
			C[j] = t.modPow(t, n250).intValue();
		}
		
		BigInteger n10_16 = BigInteger.TEN.pow(16);
		for (int i = 0; i < 250250; i ++) {
			for (int j = 0; j < A.length; j ++) {
				B[j] = A[j];
			}

			int n = C[i%500];
			//递推关系
			for (int j = 0; j < A.length; j ++) {
				if (j == n) {
					A[j] = B[j].add(B[(250+j-n)%250]).add(BigInteger.ONE).mod(n10_16);
				} else {
					A[j] = B[j].add(B[(250+j-n)%250]).mod(n10_16);
				}
			}
		}
		System.out.println(A[0]);
		System.out.println((System.currentTimeMillis()-start) + " ms");
	}

}
